#include "grafo.h"
#include "fila.h"
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_VALUE 100000000

/*
Aloca dinamicamente uma matriz
*/
float **matrix_alloc(int matrix_size){
    float **mat;
    int i,j;
    // aloca as linhas da matriz
    mat = (float **) calloc (matrix_size, sizeof(float *));
    // aloca as colunas da matriz
    for ( i = 0; i < matrix_size; i++ ) {
        mat[i] = (float*) calloc (matrix_size, sizeof(float));
    }
    return mat;
}

/*
Calcula matriz com as melhores distancias entre os vértices
*/
float **graph_FloydWarshall(float **graph, int n_vertex){
    float **res=matrix_alloc(n_vertex);   // Aloca a matriz
    int k,i,j;

    // faz uma cópia do grafo
    for(i=0;i<n_vertex;i++){
        for(j=0;j<n_vertex;j++){
            res[i][j]=graph[i][j];
        }
    }

    for(k=0;k<n_vertex;k++){
        for(j=0;j<n_vertex;j++){
            for(i=0;i<n_vertex;i++){
                if(res[i][k]==MAX_VALUE||res[k][j]==MAX_VALUE){
                    continue;
                }
                if(res[i][j]>res[i][k]+res[k][j]){
                    res[i][j]=res[i][k]+res[k][j];
                }
            }
        }
    }
    return res;
}

/*
Imprime Grafo
*/
int graph_print(float **graph,int n_vertex){
    int i,j;
    for(i=0;i<n_vertex;i++){
        for(j=0;j<n_vertex;j++){
            printf("%.1f ",graph[i][j]);
        }
        printf("\n");
    }
}

/*
Insere aresta
*/
int graph_insert(float **graph, int vertA, int vertB, float weight){
    graph[vertA][vertB]=weight;
    graph[vertB][vertA]=weight;
    return 0;
}

/*
Inicia o grafo (matriz de adjacências)
*/
float **graph_init(int n_vertex){
    float **mat;
    int i,j;

    mat=matrix_alloc(n_vertex);

    // inicia os valores
    for(i=0;i<n_vertex;i++){
        for(j=0;j<n_vertex;j++){
            if(i==j){
                mat[i][j]=0;
            }
            else{
                mat[i][j]=MAX_VALUE;
            }
        }
    }

    return mat;
}























